1. Field of the Invention
The present invention relates to routing packets among vehicles for communication in a vehicular ad hoc network (VANET).
2. Description of the Related Arts
Vehicular ad hoc networks (VANETs) are often used for wireless communications from a communication source to a communication destination. A VANET is a communication network that is comprised of moving cars with wireless communication devices. In a VANET, packets are passed on from a source to a destination via wireless communication devices on one or more vehicles. The destination is often a roadside unit (RSU) that facilitates wireless communication, such as a base station used for cellular telephone communication. Moving cars are often equipped with communication radio devices that exchange data with the RSUs.
However, the area in which such vehicles move around is much wider than the transmission range of the communication radio devices in the vehicles. For example, the following parameters may be assumed: (i) the area in which the vehicles move around is typically 2-5 km2 and has at most 10 RSU's; (ii) the speeds of the cars are about 30 miles/hour on the average and 45 miles/hour maximum; and (iii) the transmission range of the radio devices are about 200-250 meters. Thus, cars typically cannot send or receive data to/from an RSU by a single hop. Transmission of packets between a car and a destination RSU is typically carried out by multi-hop transmission over vehicle-to-vehicle communication. If there are 9 RSU's in a 3 km2 area, one RSU roughly covers 1 km2. So it would take about 5 hops (=1 km/200 m per hop) for a packet to reach an RSU.
One conventional technique for routing packets from a source to a destination in a VANET is geographic forwarding. Geographic forwarding routes packets from one car to another car based on how close the cars are to the destination d, and passes the packets to the car(s) that are geographically the closest to the destination d. In other words, the main criterion to prioritize the nearby cars for packet forwarding is their Euclidean distance to the destination d. Geographic forwarding has the advantage of fast computational speed per hop that occasionally results in short latency, since it is relatively simple to calculate the distance to destination d for every car in the proximity. However, geographic forwarding may not always select the most reliable routing path. For example, FIG. 1 illustrates a variety of routing possibilities in a VANET. According to the geographic forwarding method, Car A is selected as the next car to “hop” from source car 102, because Car A is geographically closes to the destination RSU 104. However, the vehicle for the next hop from Car A is not at an optimal position, and the geographic forwarding method will thus result in a large number of hops and large latency for complete transmission to destination RSU 104.
Another conventional technique called MDDV improves geographical forwarding by using trajectory based forwarding and opportunistic forwarding in addition to the conventional technique of geographic forwarding. Trajectory based forwarding first determines an approximate trajectory from the source to the destination on the map, and then only consider the cars that roughly follow the trajectory for the next hop. Opportunistic forwarding chooses some cars that meet certain predetermined conditions to give them the right to broadcast the packet in the proximity. By use of trajectory based forwarding and opportunistic forwarding in addition to geographic forwarding, MDDV can achieve good latency and delivery ratio, especially for arterial roads or highways where cars typically run in the same direction in general. However, MDDV may not work well in a VANET with cars driving in non-arterial roads. For example, referring to FIG. 1, Car B may be selected as the car for the next hop from source 102 to destination RSU 104, because Car B is the second closest from source vehicle 102 and is on the shortest trajectory from source vehicle 102 to destination RSU 104. However, the traffic ahead of Car B is too sparse and is thus may not be the ideal choice for complete transmission of the packet from source vehicle 102 to destination RSU 104 with short latency.
Other conventional techniques for VANET routing also suffer from other disadvantages, such as large computational time in a moving car or inefficient routing.